Search for: All records

Incremental graphs that change over time capture the changing relationships of different entities. Given that many real-world networks are extremely large, it is often necessary to partition the network over many distributed systems and solve a complex graph problem over the partitioned network. This paper presents a distributed algorithm for identifying strongly connected components (SCC) on incremental graphs. We propose a two-phase asynchronous algorithm that involves storing the intermediate results between each iteration of dynamic updates in a novel meta-graph storage format for efficient recomputation of the SCC for successive iterations. To the best of our knowledge, this is the first attempt at identifying SCC for incremental graphs across distributed compute nodes. Our experimental analysis on real and synthesized graphs shows up to 2.8x performance improvement over the state-of-the-art by reducing the overall memory utilized and improving the communication bandwidth. 

Leveraging protein-protein interaction networks to identify groups of proteins and their common functionality is an important problem in bioinformatics. Systems-level analysis of protein-protein interactions is made possible through network science and modeling of high-throughput data. From these analyses, small protein complexes are traditionally represented graphically as complete graphs or dense clusters of nodes. However, there are certain graph theoretic properties that have not been extensively studied in PPI networks, especially as they pertain to cluster discovery, such as planarity. Planarity of graphs have been used to reflect the physical constraints of real-world systems outside of bioinformatics, in areas such as mapping and imaging. Here, we investigate the planarity property in network models of protein complexes. We hypothesize that complexes represented as PPI subgraphs will tend to be planar, reflecting the actual physical interface and limits of components in the complex. When testing the planarity of known complex subgraphs in S. cerevisiae and selected mammalian PPIs, we find that a majority of validated complexes possess this planar property. We discuss the biological motivation of planar versus nonplanar subgraphs, observing that planar subgraphs tend to have longer protein components. Functional classification of planar versus nonplanar complex subgraphs reveals differences in annotation of these groups relating to cellular component organization, structural molecule activity, catalytic activity, and nucleic acid binding. These results provide a new quantitative and biologically motivated measure of real protein complexes in the network model, important for the development of future complex-finding algorithms in PPIs. Accounting for this property paves the way to new means for discovering new protein complexes and uncovering the functionality of unknown or novel proteins. s 

We propose a novel method which we call the Probabilistic Infection Model (PIM). Instead of stochastically assigning exactly one state to each agent at a time, PIM tracks the likelihood of each agent being in a particular state. Thus, a particular agent can exist in multiple disease states concurrently. Our model gives an improved resolution of transitions between states, and allows for a more comprehensive view of outbreak dynamics at the individual level. Moreover, by using a probabilistic approach, our model gives a representative understanding of the overall trajectories of simulated outbreaks without the need for numerous (order of hundreds) of repeated Monte Carlo simulations. We simulate our model over a contact network constructed using registration data of university students. We model three diseases; measles and two strains of influenza. We compare the results obtained by PIM with those obtained by simulating stochastic SEIR models over the same the contact network. The results demonstrate that the PIM can successfully replicate the averaged results from numerous simulations of a stochastic model in a single deterministic simulation. Keywords: Computational epidemics, Outbreak simulation, SEIR model 

Analyzing large dynamic networks is an important problem with applications in a wide range of disciplines. A key operation is updating the network properties as its topology changes. In this paper we present graph sparsification as an efficient abstraction for updating the properties of dynamic networks. We demonstrate the applicability of graph sparsification in updating the connected components in random and scalefree networks on shared memory systems. Our results show that the updating is scalable (10X on 16 processors for larger networks). To the best of our knowledge this is the first parallel implementation of graph sparsification. Based on these initial results, we discuss how the current implementation can be further improved and how graph sparsification can be applied to updating other network properties. 

Abstract We present the results of a search for gravitational-wave transients associated with core-collapse supernova SN 2023ixf, which was observed in the galaxy Messier 101 via optical emission on 2023 May 19, during the LIGO–Virgo–KAGRA 15th Engineering Run. We define a five-day on-source window during which an accompanying gravitational-wave signal may have occurred. No gravitational waves have been identified in data when at least two gravitational-wave observatories were operating, which covered ∼14% of this five-day window. We report the search detection efficiency for various possible gravitational-wave emission models. Considering the distance to M101 (6.7 Mpc), we derive constraints on the gravitational-wave emission mechanism of core-collapse supernovae across a broad frequency spectrum, ranging from 50 Hz to 2 kHz, where we assume the gravitational-wave emission occurred when coincident data are available in the on-source window. Considering an ellipsoid model for a rotating proto-neutron star, our search is sensitive to gravitational-wave energy 1 × 10⁻⁴M_⊙c²and luminosity 2.6 × 10⁻⁴M_⊙c²s⁻¹for a source emitting at 82 Hz. These constraints are around an order of magnitude more stringent than those obtained so far with gravitational-wave data. The constraint on the ellipticity of the proto-neutron star that is formed is as low as 1.08, at frequencies above 1200 Hz, surpassing past results. 

Abstract Continuous gravitational waves (CWs) emission from neutron stars carries information about their internal structure and equation of state, and it can provide tests of general relativity. We present a search for CWs from a set of 45 known pulsars in the first part of the fourth LIGO–Virgo–KAGRA observing run, known as O4a. We conducted a targeted search for each pulsar using three independent analysis methods considering single-harmonic and dual-harmonic emission models. We find no evidence of a CW signal in O4a data for both models and set upper limits on the signal amplitude and on the ellipticity, which quantifies the asymmetry in the neutron star mass distribution. For the single-harmonic emission model, 29 targets have the upper limit on the amplitude below the theoretical spin-down limit. The lowest upper limit on the amplitude is 6.4 × 10⁻²⁷for the young energetic pulsar J0537−6910, while the lowest constraint on the ellipticity is 8.8 × 10⁻⁹for the bright nearby millisecond pulsar J0437−4715. Additionally, for a subset of 16 targets, we performed a narrowband search that is more robust regarding the emission model, with no evidence of a signal. We also found no evidence of nonstandard polarizations as predicted by the Brans–Dicke theory. 

Abstract We present results from a search for X-ray/gamma-ray counterparts of gravitational-wave (GW) candidates from the third observing run (O3) of the LIGO–Virgo–KAGRA network using the Swift Burst Alert Telescope (Swift-BAT). The search includes 636 GW candidates received with low latency, 86 of which have been confirmed by the offline analysis and included in the third cumulative Gravitational-Wave Transient Catalogs (GWTC-3). Targeted searches were carried out on the entire GW sample using the maximum-likelihood Non-imaging Transient Reconstruction and Temporal Search pipeline on the BAT data made available via the GUANO infrastructure. We do not detect any significant electromagnetic emission that is temporally and spatially coincident with any of the GW candidates. We report flux upper limits in the 15–350 keV band as a function of sky position for all the catalog candidates. For GW candidates where the Swift-BAT false alarm rate is less than 10⁻³Hz, we compute the GW–BAT joint false alarm rate. Finally, the derived Swift-BAT upper limits are used to infer constraints on the putative electromagnetic emission associated with binary black hole mergers. 

Abstract The magnetar SGR 1935+2154 is the only known Galactic source of fast radio bursts (FRBs). FRBs from SGR 1935+2154 were first detected by the Canadian Hydrogen Intensity Mapping Experiment (CHIME)/FRB and the Survey for Transient Astronomical Radio Emission 2 in 2020 April, after the conclusion of the LIGO, Virgo, and KAGRA Collaborations’ O3 observing run. Here, we analyze four periods of gravitational wave (GW) data from the GEO600 detector coincident with four periods of FRB activity detected by CHIME/FRB, as well as X-ray glitches and X-ray bursts detected by NICER and NuSTAR close to the time of one of the FRBs. We do not detect any significant GW emission from any of the events. Instead, using a short-duration GW search (for bursts ≤1 s) we derive 50% (90%) upper limits of 10⁴⁸(10⁴⁹) erg for GWs at 300 Hz and 10⁴⁹(10⁵⁰) erg at 2 kHz, and constrain the GW-to-radio energy ratio to ≤10¹⁴−10¹⁶. We also derive upper limits from a long-duration search for bursts with durations between 1 and 10 s. These represent the strictest upper limits on concurrent GW emission from FRBs. 

Abstract We report the observation of a coalescing compact binary with component masses 2.5–4.5M_⊙and 1.2–2.0M_⊙(all measurements quoted at the 90% credible level). The gravitational-wave signal GW230529_181500 was observed during the fourth observing run of the LIGO–Virgo–KAGRA detector network on 2023 May 29 by the LIGO Livingston observatory. The primary component of the source has a mass less than 5M_⊙at 99% credibility. We cannot definitively determine from gravitational-wave data alone whether either component of the source is a neutron star or a black hole. However, given existing estimates of the maximum neutron star mass, we find the most probable interpretation of the source to be the coalescence of a neutron star with a black hole that has a mass between the most massive neutron stars and the least massive black holes observed in the Galaxy. We provisionally estimate a merger rate density of ${55}_{-47}^{+127}{\mathrm{Gpc}}^{-3}{\mathrm{yr}}^{-1}$for compact binary coalescences with properties similar to the source of GW230529_181500; assuming that the source is a neutron star–black hole merger, GW230529_181500-like sources may make up the majority of neutron star–black hole coalescences. The discovery of this system implies an increase in the expected rate of neutron star–black hole mergers with electromagnetic counterparts and provides further evidence for compact objects existing within the purported lower mass gap.